#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 6031)
#include "st.h"


bt* buybt(int x)
{
	bt* p = (bt*)malloc(sizeof(bt));
	if (!p)
	{
		perror("malloc");
		return NULL;
	}
	p->data = x;
	p->left = NULL;
	p->right = NULL;

	return p;
}

bt* creattree()
{
	bt* p1 = buybt(1);
	bt* p2 = buybt(2);
	bt* p3 = buybt(3);
	bt* p4 = buybt(4);
	bt* p5 = buybt(5);
	bt* p6 = buybt(6);

	p1->left = p2;
	p1->right = p4;
	p2->left = p3;
	p4->left = p5;
	p4->right = p6;

	return p1;
}

void btdestroy(bt* node)
{
	if (!node)
		return;

	btdestroy(node->left);
	btdestroy(node->right);
	free(node);
}

void printprev(bt* node)
{
	if (!node)
	{
		printf("N ");
		return;
	}

	printf("%d ", node->data);
	printprev(node->left);
	printprev(node->right);
}

void printmid(bt* node)
{
	if (!node)
	{
		printf("N ");
		return;
	}
	printmid(node->left);
	printf("%d ", node->data);
	printmid(node->right);
}

void printtail(bt* node)
{
	if (!node)
	{
		printf("N ");
		return;
	}
	printtail(node->left);
	printtail(node->right);
	printf("%d ", node->data);
}

void printfloor(bt* node)
{
	
}

int nodesize(bt* node)
{
	if (!node)
		return 0;

	return nodesize(node->left) + nodesize(node->right) + 1;
}

int leafsize(bt* node)
{
	if (!node)
		return 0;
	if (!(node->left && node->right))
		return 1;

	return leafsize(node->left) + leafsize(node->right);
}

int treehigh(bt* node)
{
	if (!node)
		return 0;

	int lefttree = treehigh(node->left);
	int righttree = treehigh(node->right);

	return lefttree > righttree ? lefttree + 1 : righttree + 1;
}

int knodesize(bt* node, int k)
{
	assert(k > 0);
	if (!node)
		return 0;
	if (k == 1)
		return 1;

	return knodesize(node->left, k - 1) 
		+ knodesize(node->right, k - 1);
}

bool ifsame(bt* node1, bt* node2)
{
	if (!node1 && !node2)
		return true;
	if (!node1 || !node2)
		return false;
	if (node1->data != node2->data)
		return false;
	
	return ifsame(node1->left, node2->left)
		&& ifsame(node1->right, node2->right);
}

bt* findbt(bt* node, int x)
{
	if (!node)
		return NULL;

	if (node->data == x)
		return node;

	bt* ret1 = findbt(node->left, x);
	if (ret1)
		return ret1;

	bt* ret2 = findbt(node->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

void printlayer(bt* node)
{
	Queue p;
	queueinit(&p);

	if (node)
		queuepush(&p, node->data);

	while (!queueempty(&p))
	{
		bt* front = queuefront(&p);
		printf("%d", front->data);
		queuepop(&p);

		if (node->left)
			queueback(&p);
		if (node->right)
			queueback(&p);
	}
	queuedestroy(&p);
}